//
//  ListCode.swift
//  DataSructure
//
//  Created by Clover on 2020/6/1.
//  Copyright © 2020 Clover. All rights reserved.
//

import Foundation
public class ListNode{
    var val: Int
    var next : ListNode?
    
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

class List{
    var head: ListNode?
    var tail: ListNode?
    
// MARK: - Public
    /// 测试插入方法
    public func testListNode() -> List{
        let list = List()
        list.appendToHead(1)
        list.appendToTail(5)
        list.appendToTail(3)
        list.appendToTail(2)
        list.appendToTail(4)
        list.appendToTail(2)
        return list;
    }
    
    public func printList(_ list: ListNode?) {
        var temp = list
        while temp != nil{
            print(temp!.val)
            temp = temp?.next
        }
    }
    
    /// 尾插法
    /// - Parameter val: 插入值
    func appendToTail(_ val: Int) {
        if tail == nil {
            tail = ListNode(val)
            head = tail
        }else{
            tail?.next = ListNode(val)
            tail = tail?.next
        }
    }
    
    func appendToHead(_ val: Int) {
        if head == nil {
            head = ListNode(val)
            tail = head
        }else{
           let temp = ListNode(val)
            temp.next = head;
            head = temp
        }
    }
    
    
    func getLeftList(_ head: ListNode?, _ x: Int) -> ListNode? {
        let dummy = ListNode(0)
        var pre = dummy, node = head
        while node != nil {
            if node!.val < x {
                pre.next = node
                pre = node!
            }
            node = node!.next
        }
        pre.next = nil
        return dummy.next
    }
    
    func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
        let leftDummy = ListNode(0)
        let rightDummy = ListNode(0)
        var leftPre = leftDummy, rightPre = rightDummy, node = head
        
        while node != nil {
            if node!.val < x {
                leftPre.next = node;
                leftPre = node!
            }else{
                rightPre.next = node
                rightPre = node!
            }
            node = node!.next
        }
       // 防止环
        rightPre.next = nil;
        // 拼接
        leftPre.next = rightDummy.next
        return leftDummy.next
    }
}



